package algorithm.backtracing;

import java.util.HashSet;
import java.util.Set;

/**
 * 79. Word Search
 * leetcode : https://leetcode.com/problems/word-search/
 * Difficulty : Medium
 * @Author Antony
 * @Since 2018/11/14 15:45
 */
public class WordSearch {

    public static void main(String[] args) {
        char[][] board = new char[3][4];
        board[0] = new char[]{'A','B','C','E'};
        board[1] = new char[]{'S','F','E','S'};
        board[2] = new char[]{'A','D','E','E'};

        String word = "ABCESEEEFS";
        System.out.println(exist(board, word));
        System.out.println(exist_v2(board, word));
    }


    /**
     * 加减：9ms - 84.03%
     * 异或：7ms - 100.0%
     *
     * 思路没问题，改进的地方在如何记录已经走过的路径。
     * 改进前是使用了一个额外对象 Set<String> 来保存走过的path
     * 该改进把已经走过的左表值进行了替换
     * 替换方式：
     * 1）-26 +26 是把英文字母替换成其他值
     * 2）^256 是同一个值异或两次会还原回原值（这个异或的值随便一个都可以，只要不会异或以后还是英文字母即可）
     * 显然，位运算更快
     *
     * @param board
     * @param word
     * @return
     */
    public static boolean exist_v2(char[][] board, String word) {
        int height = board.length;
        int width = board[0].length;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                boolean exist = searchChar_v2(board,word,0,i,j);
                if(exist){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean searchChar_v2(char[][] board, String word, int index, int hIdx, int wIdx){
        int height = board.length;
        int width = board[0].length;
        if(hIdx>=height || hIdx<0 || wIdx>=width || wIdx<0){
            return false;
        }
        if(board[hIdx][wIdx] == word.charAt(index)){
//            board[hIdx][wIdx] -= 26;
            board[hIdx][wIdx] ^= 256;
            if(index == word.length() - 1){
                return true;
            }else{
                boolean up = searchChar_v2(board,word,index+1,hIdx-1,wIdx);
                if(up){
                    return true;
                }
                boolean down = searchChar_v2(board,word,index+1,hIdx+1,wIdx);
                if(down){
                    return true;
                }
                boolean left = searchChar_v2(board,word,index+1,hIdx,wIdx-1);
                if(left){
                    return true;
                }
                boolean right = searchChar_v2(board,word,index+1,hIdx,wIdx+1);
                if(right){
                    return true;
                }
            }
//            board[hIdx][wIdx] += 26;
            board[hIdx][wIdx] ^= 256;
        }
        return false;
    }


    /**
     * 80ms - 9.83%
     * @param board
     * @param word
     * @return
     */
    public static boolean exist(char[][] board, String word) {
        int height = board.length;
        int width = board[0].length;
        Set<String> searchPath = new HashSet<>();
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                boolean exist = searchChar(board,word,0,i,j, searchPath);
                searchPath.clear();
                if(exist){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean searchChar(char[][] board, String word, int index, int hIdx, int wIdx, Set<String> searchPath){
        int height = board.length;
        int width = board[0].length;
        if(hIdx>=height || hIdx<0 || wIdx>=width || wIdx<0){
            return false;
        }
        String path = hIdx + "_" + wIdx;
        if(searchPath.contains(path)){
            return false;
        }
        if(board[hIdx][wIdx] == word.charAt(index)){
            searchPath.add(path);   // 如果匹配，就暂时把已走过的路径加上
            if(index == word.length() - 1){
                return true;
            }else{
                boolean up = searchChar(board,word,index+1,hIdx-1,wIdx,searchPath);
                if(up){
                    return true;
                }
                boolean down = searchChar(board,word,index+1,hIdx+1,wIdx,searchPath);
                if(down){
                    return true;
                }
                boolean left = searchChar(board,word,index+1,hIdx,wIdx-1,searchPath);
                if(left){
                    return true;
                }
                boolean right = searchChar(board,word,index+1,hIdx,wIdx+1,searchPath);
                if(right){
                    return true;
                }
            }
            searchPath.remove(path);    // 如果接下来四个都没匹配，则该层会返回false。那么将该层path移除
        }
        return false;
    }
}
